package leetcode.code0173;

import java.util.ArrayList;
import java.util.List;

import leetcode.helper.tree.TreeNode;

/**
 * 执行用时：17 ms, 在所有 Java 提交中击败了100.00%的用户
 *
 * 内存消耗：41.7 MB, 在所有 Java 提交中击败了89.09%的用户
 *
 * 通过测试用例：61 / 61
 */
public class BSTIterator {

	List<Integer> list;
	int next;
	int size;

	public BSTIterator(TreeNode root) {
		list = new ArrayList<>();
		this.f(root);
		this.next = -1;
		this.size = list.size();
	}

	private void f(TreeNode root) {
		if (root == null) {
			return;
		}
		this.f(root.left);
		list.add(root.val);
		this.f(root.right);
	}

	public int next() {
		this.next++;
		return this.list.get(next);
	}

	public boolean hasNext() {
		return this.next + 1 <= this.size;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
